package com.sunny.t2;

/**
 * 数据流求中位数
 */

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author zsunny
 * @Date 2018/9/23 11:27
 * @Mail zsunny@yeah.net
 */
public class Main {

    PriorityQueue<Integer> pq1 = new PriorityQueue<>();
    PriorityQueue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder());

    public static void main(String[] args) {

        Main main = new Main();
        int[] arr = {1,2,2,3,2,5,6,9,8,10,11};
        for(int i=0;i<arr.length;i++){
            main.deal(arr[i]);
        }
        System.out.println(main.getRes());

    }

    public void deal(int n){
        int len1 = pq1.size();
        int len2 = pq2.size();
        if(len1 == len2){
            if(len1 == 0 || (n < pq1.peek() && n > pq2.peek())){
                pq1.offer(n);
            }else if(n >= pq1.peek()){
                pq1.offer(n);
            }else if(n <= pq2.peek()){
                pq2.offer(n);
            }
        }else if(pq1.size() > pq2.size()){
            if(pq1.peek() < n){
                int tmp = pq1.poll();
                pq2.offer(tmp);
            }
            pq1.offer(n);
        }else{
            if(pq2.peek() > n){
                int tmp = pq2.poll();
                pq1.offer(tmp);
            }
            pq2.offer(n);
        }
    }

    public int getRes(){
        if(pq1.size() == pq2.size()){
            return (pq1.peek()+pq2.peek())>>1;
        }else if(pq1.size() > pq2.size()){
            return pq1.peek();
        }
        return pq2.peek();
    }

}
